A major challenge when analyzing a Circuit-under-Debug (CUD) using trace
buffers is that the mode in which the CUD is working at during online
operation may not be known beforehand. Specifically, this mode of operation
is not known at the time of the trace signal selection. Therefore,
selecting trace signals to maximize restoration for one mode of operation
may result in poor restoration if a bug is actually observed in another
mode.  Meanwhile, due to physical limitations, trace signals are typically
required to be fixed before the debugging process and remain unchanged
until the debugging process ends. Therefore the trace signal selection
procedure needs to generate a high-quality solution to ensure high
restoration over all the operation modes.

Ideally, a solution that is optimal for every mode is preferred. But this
may not be possible to achieve in modern designs which are large in size
and may have many modes of operation. Existing single-mode trace signal
selection algorithms may result in a poor restoration when evaluated over
all the operation modes. This is because these algorithms will try to push
towards the restoration in a single mode as much as possible thus they lack
a global view of restoration contributed by all the modes. For example, a
portion of the circuit is turned off during power-gating. The single-mode
selection algorithms may spend all efforts on selecting traces within the
remaining portion of the circuit. But if a bug occurs outside the
power-saving mode, the trace signals may not provide much restoration.

This work is the first to study multi-mode trace signal
selection. Specifically, in this chapter, we first extend the State
Restoration Ratio (SRR) to reflect the restoration over multiple modes and
then use that to define the Multi-mode Trace Signal Selection (MMTS)
problem as explained in Section \ref{sec:mmts}. Second, we propose a way
to generate a high quality reference for comparison among different
algorithms as elaborated in Section \ref{sec:ref}. We then propose a
procedure to merge modes with ``similar'' restoration maps in Section
\ref{sec:merging}.  We also propose an iterative algorithm to solve the
MMTS problem in Section \ref{sec:algorithm} and compare it with various
algorithms in terms of solution quality and runtime in Section
\ref{sec:results_mm}.

\newpage

\section{Problem Statement}\label{sec:mmts}
We extend the SMTS problem statement to consider restoration for multiple
operation modes as follows. Given a trace buffer of size $B\times N$, and a
set of control signals defining $M$ operation modes, the Multi-mode Trace
Signal Selection (MMTS) problem selects $B$ state elements in order to
maximize restoration over all the operation modes. To measure multi-mode
restoration, we use the following metric given by the equation below.

\begin{equation}\label{eq:msrr}\
MSRR = \sum_{m=1}^M SRR^{m}\
\end{equation}

In the above equation, $SRR^m$ is the state restoration ratio of mode $m$,
given by Equation \ref{eq:SRR}. The MSRR metric simply reflects the
summation of SRRs over all the operation mode. (To evaluate $SRR^m$ for a
single mode $m$, X-Simulation is used to compute restoration of the
remaining signals using the (same) selected trace signals but with
(different) control signal values corresponding to mode $m$. Please refer
to Algorithm \ref{alg:core} in Section \ref{sec:xsim} for details.)

We note it is intuitive to define MSRR by extending SRR in a single operation
mode because SRR has widely been used as the metric for measuring the
quality of the SMTS problem in all related works \cite{BasuM13,
ChatterjeeMB11, KoN09, LiD13,LiD14TCAD, LiuX12, ShojaeiD10}.

%Second, other variations of the above objective can also be used. %For example one can minimize the variance among the $SRR^m$, $\forall m$ modes, in addition to maximizing their summation. However, our studies showed that minimizing the variance is not a good idea because some modes in practice have a significantly higher $SRR^m$ value than others (i.e., certain control signal values may result in significantly higher amount of restoration than others). Nevertheless, our proposed procedures can likely handle other functions of $SRR^m$ (such as minimization of variance) as the multi-mode objective.
%AD: Please check the above references are suitable individually and add if any other reference is necessary

\section{A Point of Reference for High Selection Quality}\label{sec:ref}
Given a solution for MMTS, we discuss a point of reference in order to get
a sense for the quality of the corresponding $MSRR$. Given recent
advancements in the algorithms to solve the SMTS problem (e.g.,
\cite{BasuM13, ChatterjeeMB11, KoN09, LiD13,LiD14TCAD, LiuX12, ShojaeiD10}), a
natural point of reference is to (parallel-) solve SMTS for each of the $M$
modes independently and then add the corresponding $SRR^m$ values. (Note
this procedure generates $M$ distinct solutions for $M$ modes.) In
practice, this will likely be an upper bound for $MSRR$ because it is
obtained from solutions each of which is individually optimized for one
mode. We elaborate using a simple example of {\tt S38584} with only two
modes. We use the SMTS procedure in \cite{LiD13,LiD14TCAD}. The results are shown in
the table below. The two rows are when solving SMTS for modes 0 and 1. For
each trace signal selection solution, $SRR^0$ and $SRR^1$ are computed for modes 0
and 1 as reported in columns 2 and 3. The reference $MSRR$ here is
$17+8.2=25.2$.
\begin{table}[t]
  \centering
  \caption{Using SMTS solution for MMTS}
    \begin{tabular}{ccccc}
    \toprule
          & $SRR^0$  & $SRR^1$  & $MSRR$ & $MSRR$ (\%$REF$)\\
%    \midrule
    SMTS$^0$ & 17.0  & 4.3   & 21.3 & 85\% \\
    SMTS$^1$ & 14.3  & 8.2   & 22.5 & 89\% \\
    \bottomrule
    \end{tabular}%
  \label{tab:mot}
\end{table}%
%\subsection{Shortcoming of the SMTS Algorithms for the MMTS problem}\label{sec:mot}
%Figure \ref{fig:merging} shows that the restoration maps can vary over the operation modes but is it really necessary to develop a new algorithm to specifically optimize a multi-mode objective?
%Assume using an efficient single-mode strategy for selecting the reference point we select the solution corresponding to the mode which gives the maximum $MSRR$.
Consider the example in Table \ref{tab:mot} for {\tt S38584} again. We
report the ratio of the $MSRR$ of each single-mode solution with respect to
the reference case in column 5. In this example, we observe that the
solution of SMTS$^1$ has a higher $MSRR$ of 89\% than of SMTS$^0$. (Notice
that as expected, $SRR^0$ is lower in SMTS$^1$ than SMTS$^0$.) However, we
show using our proposed strategy which emphasizes multi-mode selection
throughout the procedure that it is possible to achieve a solution with
$MSRR$ that is 99\% of the reference case. %We show similar behavior of our
strategy for larger benchmarks with more modes in our experiments.%, thus
illustrating the benefits of an inherently multi-mode selection strategy.
This is partially due to the observation that there is a small (and
sometimes no) sharing in the selected trace signals of the single-mode
solutions (i.e., SMTS$^0$ and SMTS$^1$ in this example). %We observed
similar behavior in the other benchmarks as well, thus motivating for the
need of a new and inherently multi-mode selection strategy.

\section{Identifying and Merging ``Similar'' Modes}
\label{sec:merging}

\begin{figure}[t]
  \centering
  \includegraphics[width=4.0in]{figs/merge.eps}
  \caption{\small{Restoration maps of {\tt S35932} under different operation modes; \newline
      modes with similar restoration maps can be merged into a single mode.}}
    \label{fig:merging}
\end{figure}

We observe that some combinations of the values of control inputs have
similar impact in restoring the other signals, i.e., they result in similar
``restoration maps''. A restoration map shows the signals which can be
restored with corresponding values of 0 or 1, if restored \emph{only} using
the control signals. With this observation, we propose to merge the
operation modes with similar restoration maps into a single one. Mode
merging reduces the number of modes considered in MMTS and as a result,
directly translates into speed improvement of our MMTS procedure without
much loss in its solution quality.

We explain our strategies using an example. Figure \ref{fig:merging} shows
the restoration maps of ISCAS'89 benchmark {\tt S35932} for four different
modes corresponding to the values taken by the two control signals given in
\cite{LiD13,LiD14TCAD} which exist in this benchmark. Each restoration map shows the
signals which can be restored, \emph{only} when the two control signals are
applied and the remaining primary inputs do not take any values (except an
inactive reset). In each plot of Figure \ref{fig:merging}, the green dots
indicate the components (i.e., gates or state elements) which are restored
to value 0 while the black dots indicate the components which are restored
to value 1. The red dots show the components which were not
restored. (Note, Figure \ref{fig:merging} only shows about 20\% of this
benchmark; the restoration maps of the remaining 80\% were similar in the
four modes and contained mostly not-restored components.) The above
restoration maps indicate that modes 0 and 1 may be suitable to be merged
into one mode. (Similarly modes 2 and 3 are suitable to be merged.) So the
MMTS problem can be solved for two modes after merging instead of four.

Using the observations from the above example, we now propose a merging
strategy for combining \emph{two} modes into a single mode if they have a
``similar'' restoration map. Consider two modes $m_i$ and $m_j$. The number
of restored components in the two modes are denoted by $R_i$ and
$R_j$. Assume the number of common components restored by both modes is
denoted by $C_{ij}$. (This is without considering the values that they are
restored to.) We define similarity between the restoration maps of modes
$m_i$ and $m_j$ using the equation below.
\begin{equation}\label{eq:similar} S_{ij}=\frac{C_{ij}}{\max(R_i,R_j)}
\end{equation} Note in the above equation, the similarity $S_{ij}$ is a
ratio between 0 and 1. We consider two modes can be merged if $S_{ij}\geq
\alpha$, where $\alpha$ is a constant threshold set to 0.7 in our
simulations.

%A higher value of $S_{ij}$ indicates a higher ratio of common gates among the two modes so the two restoration maps are more similar. (The above strategy does not take into account if the values restored by the common components are different in the two merged modes. We did consider stricter rules for mode merging by enforcing having the same restored value for a common component but did not find it useful in further refining our merged groups in our experiment.)

When merging two modes, we replace them with a single representative
mode. It is the mode which has a restoration map with the highest number of
restored components. 

%Note, this restoration map may be slightly different than the restoration map of the other mode because (1) the values that the common components are restored to may be different in the two maps, and (2) if the similarity ratio is below 1, it means there are additional and uncommon restored components which are not shared among the two modes.

Next, we extend the strategy for combining two modes in order to combine
multiple modes. We start by visiting each mode exactly once and try to
combine it with \emph{one} of the existing modes. Here an existing mode can
be a not-visited mode, or a mode representing merging of previously-visited
modes. Specifically, when visiting mode $m_i$, if we find it can be merged
with more than one of the existing modes, we only merge it with the mode
$m_j$ with the highest similarity with $m_i$ (i.e., $S_{ij}$ is highest
compared to the other modes which can be merged with $m_i$). The process
terminates when all (unmerged) modes are visited once.

%In the above strategy, the order for visiting the modes does not matter because by setting our similarity threshold to a high value ($\alpha=0.7$), in practice we never run in conflict in assignment. See Figure 1 which has $S_{01}\approx 0.7$ for modes 0 and 1, for an example. %(e.g., modes $m_1$ and $m_2$ can be merged, $m_1$ and $m_3$ can also be merged but modes $m_1$, $m_2$, $m_3$ can not be merged).


